#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

#include <iostream>
#include <string>
#include <cstdlib>
#include <sstream>
#include <map>
using std::ostream;
using std::ostringstream;
using std::string;
using std::abs;

template <class T> class Polynomial;

template <class T>
const Polynomial<T> operator*
(const Polynomial<T> & lhs, const Polynomial<T> & rhs);

template <class T = int>
class Polynomial {
public:
    Polynomial () {};
    Polynomial (T*, const size_t);
    virtual ~Polynomial () {};

    string str () const;

    const Polynomial& operator+= (const Polynomial &);
    const Polynomial& operator-= (const Polynomial &);
    const Polynomial& operator*= (const Polynomial & rhs)
    {
        *this = *this * rhs;
    }

    friend const Polynomial<T> operator* <T>
    (const Polynomial<T> & lhs, const Polynomial<T> & rhs);

    bool operator== (const Polynomial & rhs)
    {
        return elements == rhs.elements;
    }

    bool operator!= (const Polynomial & rhs)
    {
        return !(*this != rhs);
    }

    T & operator[] (int index)
    {
        return elements[index];
    }

    T operator[] (int index) const
    {
        return elements[index];
    }

private:
    typedef std::map<int, T> elements_t;
    mutable elements_t elements;
};

template <class T>
inline ostream & operator<< (ostream & lhs, const Polynomial<T> & rhs)
{
    lhs << rhs.str ();
    return lhs;
}

template <class T>
inline const Polynomial<T> operator+ 
(const Polynomial<T> & lhs, const Polynomial<T> & rhs)
{
    return Polynomial<T> (lhs) += rhs;
}

template <class T>
inline const Polynomial<T> operator- 
(const Polynomial<T> & lhs, const Polynomial<T> & rhs)
{
    return Polynomial<T> (lhs) -= rhs;
}

template <class T>
Polynomial<T>::Polynomial (T* items, const size_t size)
{
    size_t i;
    for (i = 0; i < size; i++) {
        if (items[i] != 0)
            (*this)[i] = items[i];
    }
}

template <class T>
string Polynomial<T>::str () const
{
    if (elements.size () == 0)
        return string ("0");

    ostringstream tmp;
    bool first = true;

    typename elements_t::const_iterator it;
    for (it = elements.begin ();it != elements.end (); it++)
    {
        if (it->second != 0)
        {
            if (first)
            {
                if (it->second < 0)
                    tmp << "-";
                first = false;
            }
            else
                if (it->second < 0)
                    tmp << " - ";
                else
                    tmp << " + ";

            if (abs (it->second) != 1)
                tmp << abs (it->second);
            if (it->first)
            {
                tmp << "x";
                if (it->first != 1)
                    tmp << "^" << it->first;
            }
        }
    }

    return tmp.str ();
}

template <class T>
const Polynomial<T>& Polynomial<T>::operator+= (const Polynomial & a)
{
    typename elements_t::const_iterator it;
    for (it = a.elements.begin (); it != a.elements.end (); it++)
        elements[it->first] += it->second;

    return *this;
}

template <class T>
const Polynomial<T>& Polynomial<T>::operator-= (const Polynomial<T> & a)
{
    typename elements_t::const_iterator it;
    for (it = a.elements.begin (); it != a.elements.end (); it++)
        elements[it->first] -= it->second;

    return *this;
}

template <class T>
const Polynomial<T> operator*
(const Polynomial<T> & lhs, const Polynomial<T> & rhs)
{
    Polynomial<T> tmp;
    typename Polynomial<T>::elements_t::const_iterator it1;
    typename Polynomial<T>::elements_t::const_iterator it2;

    for (it1 = lhs.elements.begin (); it1 != lhs.elements.end (); ++it1)
        for (it2 = rhs.elements.begin (); it2 != rhs.elements.end (); ++it2)
            tmp[it1->first + it2->first] += it1->second * it2->second;

    return tmp;
}

#endif /* end of include guard: POLYNOMIAL_H */
